There exist numerous algorithms for the standard routing problem, in which a network is modeled as a directed graph, and it is assumed that traffic from one link can always be relayed to its consecutive link. Among these algorithms, the most efficient one is the well-known Dijkstra algorithm, which has been adopted for use in many of the common link-state routing protocols, such as Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), and Private Network to Network Interface (PNNI).
An important class of routing problem pertains to dynamically searching for an optimal lightpath between two edge nodes of an optical network. The path consists of one or more optical links, each link having a dedicated wavelength for the path. The wavelength, or optical channel, assigned to the path may not be the same on every link. Every time the wavelength assignment changes along the path, special wavelength conversion equipment, e.g., an optical-electrical-optical (OEO) conversion device, is required.
In optical network routing, both routing and wavelength assignment have to be considered simultaneously. In addition, since there may not be a full OEO conversion capability at every node, traffic arriving at a node on one wavelength of a link may not be able to be relayed to another wavelength of a consecutive link of the lightpath. Therefore, the standard graph model cannot be used directly.
In “Lightpath (Wavelength) Routing in Large WDM Networks”, Chlamtac et. al., IEEE Journal on Selected Areas in Communications, Vol. 14, No. 5, June 1996, it is proposed to convert the original graph to a new, matrix-like structure with m rows and N columns (N and m being the number of network nodes and wavelengths respectively), with each column corresponding to a node and each row corresponding to a wavelength. Links in the horizontal direction represent connectivity between neighboring nodes, using the available wavelengths on the optical fibers that interconnect the physical nodes. Links in the vertical direction represent connectivity between different wavelengths within a single physical node that are made available by OEO transmitters and receivers. The resulting graph is called a “wavelength graph.” Chlamtac et al. further derive a routing and wavelength assignment algorithm, referred to as the Shortest Path Algorithm for the Wavelength Graph (SPAWG), with computation complexity of O{(N+m)Nm)}. However, the SPAWG algorithm is understood to contain an error and therefore is not practically available. Moreover, the SPAWG algorithm is not Dijkstra-based and thus is difficult to integrate with standard routing protocols such as OSPF.